/**************************************************************
  > File Name: 4.c
  > Author: LuoLiang
  > Mail: 1204553475@qq.com 
  > Created Time: 2022年02月06日 星期日 13时15分36秒
 **************************************************************/

#include <stdio.h>
#include <stdlib.h>


/**
 *找出连续子序列的最大和
 *
 */
int func(int *buf, int n)
{
	int *dp = calloc(n,sizeof(int));
	int max = 0;

	dp[n-1] = buf[n-1];
	for (int i = n-2;i >= 0; i--)
	{
		dp[i] = buf[i] + dp[i+1] > buf[i] ? buf[i] + dp[i+1] : buf[i];
	}

	max = dp[0];
	for (int i = 1; i < n; i++)
	{
		if (dp[i] > max)
			max = dp[i];
	}
	return max;
}


int main(int argc,char **argv)
{
	int arr[] = {100,-30,3,-4,2,-1,2,6,-5,4};
	int ret;

	ret = func(arr,sizeof(arr) / sizeof(*arr));
	printf("%d\n",ret);


    exit(0);
}
